﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0064_IntervalIntersection : IAlgorithm
    {
        // 986. 区间列表的交集

        // 给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。
        // 每个区间列表都是成对 不相交 的，并且 已经排序 。
        // 返回这 两个区间列表的交集 。
        // 形式上，闭区间[a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。
        // 两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3]和[2, 4] 的交集为[2, 3] 。

        // 提示：
        //  0 <= firstList.length, secondList.length <= 1000
        //  firstList.length + secondList.length >= 1
        //  0 <= starti<endi <= 10^9
        //  endi<starti+1
        //  0 <= startj<endj <= 10^9
        //  endj<startj+1

        public void Test()
        {
            // 算法参数定义
            var firstList = new int[][] {
                new int[]{ 0, 2 },
                new int[]{ 5, 10 },
                new int[]{ 13, 23 },
                new int[]{ 24, 25 }
            };
            var secondList = new int[][] {
                new int[]{ 1,5 },
                new int[]{ 8,12 },
                new int[]{ 15,24 },
                new int[]{ 25, 26 }
            };
            // 算法执行与打印
            var res = IntervalIntersection(firstList, secondList);
            foreach (var item in res)
            {
                foreach (var iitem in item)
                {
                    Console.Write(iitem + " ");
                }
                Console.WriteLine();
            }
        }

        // 算法
        public int[][] IntervalIntersection(int[][] firstList, int[][] secondList)
        {
            var res = new List<int[]>();
            if (firstList.Length == 0 || secondList.Length == 0)
                return res.ToArray();
            int i = 0, j = 0;
            while (i < firstList.Length && j < secondList.Length)
            {
                var s = Math.Max(firstList[i][0], secondList[j][0]);
                var e = Math.Min(firstList[i][1], secondList[j][1]);
                if (s <= e)
                    res.Add(new int[] { s, e });
                if (firstList[i][1] > secondList[j][1])
                    j++;
                else
                    i++;
            }
            return res.ToArray();
        }
    }
}
